package algorithm.leetcode.I601to800;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 排序后,创建dp数组,含义是当前最大元素为k时可以获取的最大点数,长度为max-min+2
 * 递推关系: dp[k] = max(dp[k-1], dp[k-2]+k*ktimes),即不删当前值为k的元素和删当前元素比谁更大
 * 有点想那个打家劫舍,股票之类的,多状态dp
 *
 */

public class Q740 {

    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> times = new HashMap<>();
        Arrays.sort(nums);
        
        for (int num : nums) {
            times.put(num, times.getOrDefault(num, 0) + 1);
        }

        int[] dp = new int[nums[nums.length-1]-nums[0]+2];
        dp[0] = 0;
        dp[1] = times.get(nums[0]) * nums[0]; // nums中的数字保证都是正的
        int res = dp[1];
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i-2] + times.getOrDefault(nums[0]+i-1, 0) * (nums[0]+i-1), dp[i-1]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
    
}
